public class Leetcode {
}
//leetcode:2:：两数相加
class Solution1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null,tail = null;
        int carry = 0;
        while(l1 != null || l2 != null){
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if(head == null){
                head = tail = new ListNode(sum%10);
            }else{
                tail.next = new ListNode(sum%10);
                tail = tail.next;
            }
            carry = sum / 10;
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }
        if(carry > 0){
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

//leetcode:143:：重排链表
class Solution2 {
    public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null ){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode head2 = new ListNode(-1);
        ListNode cur = slow.next;
        slow.next = null;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = curN;
        }
        ListNode cur1 = head2.next;
        while(head != null && cur1 != null){
            ListNode headNext = head.next;
            ListNode curNext = cur1.next;
            head.next = cur1;
            cur1.next = headNext;
            head = headNext;
            cur1 = curNext;
        }
    }
}